In recent years, processing of electronic data has increased continuously. With the processing of the data also the exchange of the data has increased. This is also true for data that have to be protected against unauthorized reading or writing of the data. For this, encryption systems have been developed that are widespread, for example, public key encryption systems.
Private data are data that an owner of the private data does not want to share with a further party. Such private data may for example be legally protected because they may belong to a protected privacy area of a person. In a further example, private data may also be an amount of money that a person is willing to pay for an acquisition of an object. Furthermore, private data may also be a demanded amount of money for which a further person is willing to sell the object.
Yao's millionaires problem involves a comparison of private data. In an article with title “Protocols for Secure Computations” for the Proceedings of the annual IEEE Symposium on Foundations of Computer Science 23, 1982, A. Yao defined the millionaire's problem: two millionaires want compare an amount of money that each one has without revealing the amount of money to each other. A plurality of solutions has been suggested to Yao's millionaire problem some of which involve a third party. Such a third party has to be found by the two millionaires and may not be available. Two-party solutions involve only the two parties that own the two private values that are desired to be compared. An efficient two-party solution has been described by M. Fischlin in a publication titled “A Cost-Effective Pay-Per-Multiplication Comparison Method for Millionaires” in RSA Security Cryptographer's Track, 2001. The solution is efficient, that is, allows for a high-performance computation of a comparison of two private values. The solution has a probability for an incorrect result of the comparison, but the probability can be reduced to low values by using variants of the solution that require more computational efforts.